1238F - The Maximum Subtree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
vector <int> adj[300001];
int dp[300001][2];
void dfs (int pos, int par) {
    vector <int> ll;
    dp[pos][1] = (int)adj[pos].size() - 1;
    for (auto j : adj[pos]) {
        if (j == par) continue;
        dfs(j, pos);
        dp[pos][0] = max(dp[pos][0], dp[j][0]);
        if ((int)adj[j].size() != 1) {
            ll.push_back(dp[j][1]);
            dp[pos][1] = max(dp[pos][1], (int)adj[pos].size() + dp[j][1] - 1);
        }
    }
    sort(ll.begin(), ll.end()); reverse(ll.begin(), ll.end());
    int x = (int)adj[pos].size() + 1;
    if (ll.size() == 0) {
        dp[pos][0] = max(dp[pos][0], (int)adj[pos].size() + 1);
    } else if (ll.size() == 1) {
        dp[pos][0] = max(dp[pos][0], (int)adj[pos].size() + 1 + ll[0]);
    } else {
        dp[pos][0] = max(dp[pos][0], (int)adj[pos].size() + 1 + ll[0] + ll[1]);
    }
}
int main () {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            adj[i].clear();
            dp[i][0] = 0;
            dp[i][1] = 0;
        }
        for (int i = 1; i < n; i++) {
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        if (n == 2) {
            cout << 2 << '\n'; continue;
        }
        int root; for (int i = 1; i <= n; i++) if (adj[i].size() > 1) root = i;
        dfs(root, -1);
        cout << dp[root][0] << '\n';
    }
}